package sort;

public class GuiBingMoXie {
    int[] temp;
    public void guibingSort(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        int lo = 0;
        int hi = nums.length - 1;
        temp = new int[nums.length];
        sort(nums, lo, hi, temp);
    }

    public void sort(int[] nums, int lo, int hi, int[] temp) {
        if (lo >= hi) {
            return;
        }
        int mid = (lo + hi) / 2;
        sort(nums, lo, mid, temp);
        sort(nums, mid + 1, hi, temp);
        merge(nums, lo, mid, hi, temp);
    }

    public void merge(int[] nums, int lo, int mid, int hi, int[] temp) {
        int i = 0;
        int j = lo;
        int k = mid + 1;
        //todo:自己默写这一块的逻辑不对
//        while (nums[j]<nums[k]){
//            temp[i++]=nums[j++];
//        }
//       temp[i++]=nums[k++];

        while (j < mid + 1 && k <=hi) {
            if (nums[j] < nums[k]) {
                temp[i++] = nums[j++];
            }
            //todo:千万不能少些ｅｌｓｅ　　习惯性少写else
            else {
                temp[i++] = nums[k++];

            }

        }
        while (j < mid + 1) {
            temp[i++] = nums[j++];
        }
        while (k <=hi) {
            temp[i++] = nums[k++];
        }
        //todo:优化：
//        int i1=0;
//        for (int l = lo; l < hi; l++) {
//            nums[l]=temp[i1++];
//        }

        for (int t = 0; t < i; t++) {
            nums[lo + t] = temp[t];
        }

    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 3};
        GuiBingMoXie guiBingMoXie = new GuiBingMoXie();
        guiBingMoXie.guibingSort(nums);
        for (int a : nums
        ) {
            System.out.println(a);

        }

    }


}
